package foundation.图论.最短路;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * <strong> {@code A星} </strong>
 * <p>grid[i][j] == 0 代表障碍</p>
 * <p>grid[i][j] == 1 代表道路</p>
 * <p>返回从(startX,startY) -> (targetX,targetY) 的最短路径</p>
 */
public class AStar {
    public static int[] move = {-1, 0, 1, 0, -1};


    private static int minDistance(int[][] grid, int startX, int startY, int targetX, int targetY) {
        if (grid[startX][startY] == 0 || grid[targetX][targetY] == 0) return -1;
        int n = grid.length;
        int m = grid[0].length;
        int[][] dist = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                dist[i][j] = Integer.MAX_VALUE;
            }
        }
        dist[startX][startY] = 1;
        boolean[][] visited = new boolean[n][m];
        // a[0]:x  a[1]:y  a[2]: 距离target的预估距离
        PriorityQueue<int[]> heap = new PriorityQueue<>(Comparator.comparingInt(a -> a[2]));
        heap.add(new int[]{startX, startY, dist[startX][startY] + getDist(startX, startY, targetX, targetY)});
        while (!heap.isEmpty()) {
            int[] poll = heap.poll();
            int cx = poll[0], cy = poll[1];
            if (visited[cx][cy]) continue;
            visited[cx][cy] = true;
            if (cx == targetX && cy == targetY) {
                return dist[targetX][targetY];
            }
            for (int i = 0; i < 4; i++) {
                int nx = cx + move[i];
                int ny = cy + move[i + 1];
                if (0 <= nx && nx < n && 0 <= ny && ny < m
                        && grid[nx][ny] == 1
                        && !visited[nx][ny]
                        && dist[cx][cy] + 1 < dist[nx][ny]) {
                    dist[nx][ny] = dist[cx][cy] + 1;
                    heap.add(new int[]{nx, ny, dist[nx][ny] + getDist(nx, ny, targetX, targetY)});
                }
            }
        }
        return -1;
    }


    private static int getDist(int x, int y, int tx, int ty) {
        return Math.abs(x - tx) + Math.abs(y - ty);
    }

    public static void main(String[] args) {
        int[][] grid = {
                {1, 0, 0, 1},
                {1, 1, 0, 1},
                {1, 1, 1, 1}
        };
        int startX = 0;
        int startY = 0;
        int targetX = 0;
        int targetY = 3;
        System.out.println(minDistance(grid, startX, startY, targetX, targetY));
    }

}
